#!/usr/bin/python3
# _*_ coding:utf-8 _*_

import random


def sift(ls,low,high):
    i=low
    j=2*i+1
    tmp=ls[low]
    while j<=high:
        # 当ls[j+1] < ls[j] 要建的是小根堆,如果是大于就是大根堆
        if j+1<=high and ls[j+1]<ls[j]: 
           j=j+1
        if ls[j]<tmp:
            ls[i]=ls[j]
            i=j
            j=2*i+1
        else:
            break
    ls[i]=tmp


def topk(ls,k):
    heap=ls[0:k]
    for i in range((k-2)//2,-1,-1):
        sift(heap,i,k-1)

    for i in range(k,len(ls)-1):
        if ls[i]>heap[0]:
            heap[0]=ls[i]
            sift(heap,0,k-1)
    
    for i in range(k-1,-1,-1):
        heap[0],heap[i]=heap[i],heap[0]
        sift(heap,0,i-1)
    return heap


lst=[random.randint(1,10000000) for _ in range(10000)]
# lst=list(range(100000))
# random.shuffle(lst)
res=topk(lst,10)
for i,v in enumerate(res):
    if i+1<10:
        print(i+1,' ----',v)
    else:    
        print(i+1,'----',v)

